#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define NUM 16

typedef struct
{
    char name[32];
    int age;
    char address[32];
    char phone_number[32];
} telep_book;

typedef struct node
{
    telep_book data;
    struct node *next;
} Hash;

typedef struct
{
    int size;
    int num;
    Hash *hash[];
} hash_table;

hash_table *hash_init(int size)
{
    hash_table *table = calloc(1, sizeof(int) + sizeof(Hash *) * size);
    table->size = size;
    for (int i = 0; i < size; i++)
    {
        table->hash[i] = calloc(1, sizeof(Hash));
        table->hash[i]->next = NULL;
    }

    return table;
}

typedef enum
{
    E_Cal_Remainder = 0,         // 计算 字符串之和, 求余数
    E_Cal_Remained_Displace = 1, // 计算 字符位移之和, 求余数
} E_Cal_Mothod;
static int Default_Cal_Mothod = E_Cal_Remained_Displace;

int cal_string_key(const char *key, int size, E_Cal_Mothod cal_mothod)
{
    int sum = 0;
    int key_len = strlen(key);
    switch (cal_mothod)
    {
    case E_Cal_Remainder:
        for (int i = 0; i < key_len; i++)
        {
            sum += *(key + i);
        }
        break;
    case E_Cal_Remained_Displace:;
        int shift_bit = 0;
        for (int i = 0; i < key_len; i++, shift_bit++)
        {
            sum += (*(key + i) << shift_bit);
            if (shift_bit > 16) // 1<<24导致sum过大, 控制位移大小
                shift_bit = 0;
        }
        break;
    default:
        fprintf(stderr, "not support cal mothod %d", cal_mothod);
        exit(1);
        break;
    }

    return sum % size;
}

Hash *hash_insert(hash_table *table, const char *_key, telep_book *book)
{
    int key = cal_string_key(_key, table->size, Default_Cal_Mothod);
    Hash *index = table->hash[key];
    Hash *new = calloc(1, sizeof(Hash));
    memcpy(&new->data, book, sizeof(new->data));
    new->next = index->next;
    index->next = new;

    return new;
}

void hash_show(hash_table *table)
{
    for (int i = 0; i < table->size; i++)
    {
        Hash *index = table->hash[i];
        printf("key[%d]\n", i);
        while (index->next != NULL)
        {
            telep_book *book = &index->next->data;
            printf("    --> name:%s age:%d address:%s phone_number:%s\n", book->name,
                   book->age, book->address, book->phone_number);

            index = index->next;
        }
    }
}

int hash_search(hash_table *table, const char *_key, telep_book *dst)
{
    int key = cal_string_key(_key, table->size, Default_Cal_Mothod);
    Hash *index = table->hash[key];
    while (index->next != NULL)
    {
        if (strncmp(index->next->data.name, _key, sizeof(dst->name)) == 0)
        {
            memcpy(dst, &index->next->data, sizeof(*dst));
            return 1;
        }
        index = index->next;
    }

    return 0;
}

int hash_del(hash_table *table, const char *_key)
{
    int key = cal_string_key(_key, table->size, Default_Cal_Mothod);
    Hash *index = table->hash[key];
    while (index->next != NULL)
    {
        if (strcmp(index->next->data.name, _key) == 0)
        {
            // memcpy(dst, &index->next->data, sizeof(*dst));
            Hash *tmp = index->next;
            index->next = tmp->next;
            free(tmp);
            return 1;
        }
        index = index->next;
    }

    return 0;
}

void hash_free(hash_table *table)
{
    for (int i = 0; i < table->size; i++)
    {
        Hash *index = table->hash[i];
        while (index->next != NULL)
        {
            Hash *tmp = index->next;
            index->next = tmp->next;
            free(tmp);
        }
        free(index);
        index = NULL;
    }
    free(table);
}

int main(int argc, char *argv[])
{
    if (argc == 1)
    {
        Default_Cal_Mothod = E_Cal_Remainder;
        printf("求余数\n");
    }
    else
    {
        Default_Cal_Mothod = E_Cal_Remained_Displace;
        printf("位移求余数\n");
    }

    hash_table *table = hash_init(NUM);
    telep_book a[] = {
        {"lilisi", 18, "CH_SZ_BaoAn", "123456"},
        {"Malike", 19, "CH_SZ_LongHua", "456789"},
        {"Jack", 20, "CH_SZ_NanShang", "654321"},
        {"Aiden", 21, "CH_SZ_XiLi", "987654"},
    };
    int a_len = sizeof(a) / sizeof(a[0]);
    int i;
    for (i = 0; i < a_len; i++)
    {
        hash_insert(table, a[i].name, &a[i]);
    }
    hash_show(table);

    char b[4][32] = {"lilisi", "Helen", "Jack", "BuNanKe"};
    int b_len = sizeof(b) / sizeof(b[0]);
    for (i = 0; i < b_len; i++)
    {
        telep_book book;
        int ret = hash_search(table, b[i], &book);
        if (ret)
            printf("find %s, age:%d address:%s phone_num:%s\n", b[i], book.age, book.address, book.phone_number);
        else
            printf("not find %s\n", b[i]);
    }

    hash_del(table, "lilisi");
    hash_show(table);

    hash_free(table);

    return 0;
}
